#include "ahoCorasick.h"

AhoCorasick::Match::Match(int newPatternIndex, int newTextPosition)
:patternIndex(newPatternIndex), textPosition(newTextPosition) {}

AhoCorasick::TreeNode::TreeNode(int newParentIndex, unsigned char newWayChar)
:parentIndex(newParentIndex), suffLink(-1), suffTermLink(-1), isTermNode(false), wayChar(newWayChar) {}


size_t AhoCorasick::size() const {
    return nodes.size();
}

AhoCorasick::AhoCorasick()
:nodes(1, TreeNode(0, '$')) {}

int AhoCorasick::getAutoGoNode(int nodeIndex, unsigned char transChar) {
    if (nodes[nodeIndex].autoGoNode.find(transChar) == nodes[nodeIndex].autoGoNode.end()) { //если переход по символу transChar еще не вычислен (используем ленивую динамику)
        MapIterator it = nodes[nodeIndex].nextCharNode.find(transChar); //ищем ребро с transChar
        if (it != nodes[nodeIndex].nextCharNode.end()) { //если такое ребро существует, то добавляем в autoGoNode этот переход
            nodes[nodeIndex].autoGoNode.insert(std::pair<char, int>(transChar, it->second));
        } else { //если ребра не существует
            if (nodeIndex == 0) { //если вершина - корень
                nodes[nodeIndex].autoGoNode.insert(std::pair<char, int>(transChar, 0)); //то добавляем переход
            } else { //иначе
                nodes[nodeIndex].autoGoNode.insert(std::pair<char, int>(transChar, getAutoGoNode(getSuffLink(nodeIndex), transChar))); //иначе добавляем в autoGoNode вершину, которую поучаем при переходе по transChar из вершины полученной по суффиксной ссылке nodeIndex
            }
        }
    }
    return nodes[nodeIndex].autoGoNode.find(transChar)->second;
}

int AhoCorasick::getSuffLink(int nodeIndex) {
    if (nodes[nodeIndex].suffLink == -1) { //если суффиксная ссылка еще не вычислена
        if (nodeIndex == 0 || nodes[nodeIndex].parentIndex == 0) { //если наша вершина это корень или ее предок это корень
            nodes[nodeIndex].suffLink = 0; //то суффиксная ссылка должна указывать на корень
        } else { //в противном случаем мы переходим по суффиксной ссылке предка nodeIndex и из полученной вершины переходим по символу, соединяещему вершину nodeIndex с ее предком
            nodes[nodeIndex].suffLink = getAutoGoNode(getSuffLink(nodes[nodeIndex].parentIndex), nodes[nodeIndex].wayChar);
        }
    }
    return nodes[nodeIndex].suffLink;
}

int AhoCorasick::getSuffTermLink(int nodeIndex) {
    if (nodes[nodeIndex].suffTermLink == -1) { //если хорошая суффиксная ссылка еще не вычислена
        int currentNodeSuffLink = getSuffLink(nodeIndex); //сначала берем значение обычной суффиксной ссылки
        if (currentNodeSuffLink == 0) { //если она указывает на корень, то и терминальная суффиксная ссылка будет указывать на корень
            nodes[nodeIndex].suffTermLink = 0;
        } else { //в противном случае
            if (nodes[currentNodeSuffLink].isTermNode) { //если вершина по текущей ссылке терминальная
                nodes[nodeIndex].suffTermLink = currentNodeSuffLink; //то эта ссылка является хорошей
            } else { //иначе
                nodes[nodeIndex].suffTermLink = getSuffLink(currentNodeSuffLink); //иначе переходим по суффиксной ссылке вершины полученной по текущей суффиксной ссылке, пока не достигнем терминальной вершины или корня
            }
        }
    }
    return nodes[nodeIndex].suffTermLink;
}

void AhoCorasick::addPattern(const std::string& pattern) {
    int currentNodeIndex = 0;
    for (size_t charIndex = 0; charIndex < pattern.size(); ++charIndex) { //идем по всем буквам из pattern
        unsigned char currentChar = pattern[charIndex] - AhoCorasick::ALPHABET_START; //получаем код буквы, считая что код 'a' это 0
        MapIterator it = nodes[currentNodeIndex].nextCharNode.find(currentChar); //ищем ребро из 0-ой вершины с буквой currentChar на нем
        int nextNodeIndex;
        if (it == nodes[currentNodeIndex].nextCharNode.end()) { //если такое ребро не найдено
            nextNodeIndex = nodes[currentNodeIndex].nextCharNode.insert(std::pair<char, int>(currentChar, nodes.size())).first->second; //вычисляем номер вершины которую добавляем
            nodes.push_back(TreeNode(currentNodeIndex, currentChar)); //и добавляем вершину в бор
        } else { //иначе
            nextNodeIndex = it->second; //вычисляем номер вершины в которую переходим по currentChar
        }
        currentNodeIndex = nextNodeIndex; //обновляем значение текущей вершины
    }
    nodes[currentNodeIndex].isTermNode = true; //делаем конечную вершину терминальной
    nodes[currentNodeIndex].patternIndex = patterns.size(); //присваеваем pattern-у номер
    patterns.push_back(pattern); //добавляем pattern в массив pattern-ов
}

void AhoCorasick::addPattern(const std::vector<std::string> patterns) {
    for (size_t patternIndex = 0; patternIndex < patterns.size(); ++patternIndex) {
        addPattern(patterns[patternIndex]);
    }
}

std::string AhoCorasick::getPattern(int patternIndex) const {
    return patterns[patternIndex];
}

void AhoCorasick::searchMatches(int nodeIndex, int textIndex, std::vector<Match>& matches) {
    while (nodeIndex != 0) { //пока вершина не корень
        if (nodes[nodeIndex].isTermNode) { //если вершина является терминальной
            int patternIndex = nodes[nodeIndex].patternIndex; //то вычисляем номер pattern-а которому она соответствует
            matches.push_back(Match(patternIndex, textIndex + 1 - patterns[patternIndex].size())); //и добавляем значение в matches
        }
        nodeIndex = getSuffTermLink(nodeIndex); //иначе переходим по терминальной суффиксной ссылке и повторяем процедуру
    }
}

void AhoCorasick::getMatches(const std::string& text,  std::vector<Match>& matches) {
    int currentNodeIndex = 0;
    for (size_t charIndex = 0; charIndex < text.size(); ++charIndex) { //идем по всем символам из text
        unsigned char currentChar = text[charIndex] - AhoCorasick::ALPHABET_START; //вычисляем номер текущего символа
        currentNodeIndex = getAutoGoNode(currentNodeIndex, currentChar); //переходим из currentNodeIndex в currentNodeIndex и присваиваем это значение currentNodeIndex
        searchMatches(currentNodeIndex, charIndex, matches); //проверяем подходит ли нам текущее слово
    }
}